HDOJ 3790 【Dijkstra】最短路径问题

【题目描述】

http://acm.hdu.edu.cn/showproblem.php?pid=3790

【思路】

松弛操作每更新一条边，不管被更新的点的cost值是否最小都要被更新，这里wa了3发…..
当被更新的点的dis值相等时再检查cost的值是否最小。

#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;

const int Max=2100000;
typedef pair<int,int> Pair;
priority_queue<Pair,vector<Pair>,greater<Pair> > Q;

int n,S,T,tail,dis[1100],head[1100],cost[1100];

struct data
{
      int c,w,to,next;
}k,edge[210000];

void build(int u,int v,int d,int p)
{
      edge[tail].w=d;
      edge[tail].to=v;
      edge[tail].c=p;
      edge[tail].next=head[u];
      head[u]=tail++;
}

void Dij()
{
      Pair s,u;
      int v,val;

      dis[S]=0;
      cost[S]=0;
      s.first=0;
      s.second=S;
      Q.push(s);

      while (!Q.empty())
      {
            u=Q.top();
            Q.pop();
            v=u.second;
            val=u.first;
            if (dis[v]<val) continue;

            for (int i=head[v];i!=-1;i=edge[i].next)
            {
                  k=edge[i];
                  if (dis[k.to]>dis[v]+k.w)
                  {
                        dis[k.to]=dis[v]+k.w;
                        Q.push(Pair(dis[k.to],k.to));
                        cost[k.to]=cost[v]+k.c;
                  }
                  else if (dis[k.to]==dis[v]+k.w)
                        cost[k.to]=min(cost[k.to],cost[v]+k.c);
            }
      }
}

int main()
{
      int n,m,u,v,d,p;

      while (scanf("%d%d",&n,&m)!=EOF)
      {
            if (!n && !m) break;

            tail=0;
            for (int i=0;i<1100;i++) head[i]=-1;
            for (int i=0;i<1100;i++) dis[i]=Max;
            for (int i=0;i<1100;i++) cost[i]=Max;

            for (int i=1;i<=m;i++)
            {
                  scanf("%d%d%d%d",&u,&v,&d,&p);
                  build(u,v,d,p);
                  build(v,u,d,p);
            }

            scanf("%d%d",&S,&T);

            Dij();
            printf("%d %d\n",dis[T],cost[T]);
      }

      return 0;
}

while (!q.empty())
{
	xx = q.front();
	q.pop();
	QM[xx] = 0;

	for (int i = 1; i <= nNum; ++i)
	{
		if (dist[i] > dist[xx] + g[xx][i])
		{
			dist[i] = dist[xx] + g[xx][i];
			px[i] = px[xx] + cost[xx][i];
			if (QM[i] == 0)
			{
				QM[i] = 1;
				q.push(i);
			}
		}
		else if (dist[i] == dist[xx] + g[xx][i] && px[i] > px[xx] + cost[xx][i])
		{
			px[i] = px[xx] + cost[xx][i];
		}
	}
}